Electronic and online auctions provide a convenient mechanism for buying and selling goods. In a simple auction, sellers offer for sale one or more individual items, and buyers bid on these items. The highest bid wins the item.
In combinatorial auctions, potential buyers place bids on combinations of items called packages, as opposed to placing a bid on a single item. Generally, each bidder determines a value for each package being offered. Bidders are not aware of values or bids of other competing bidders. For instance, each bidder specifies different prices for different combinations of good.
Combinatorial auctions are difficult to optimize, and the winner determination problem (WDP) in such auctions is complex. In other words, it is difficult to determine an efficient allocation of goods once the bids have been submitted to the auctioneer. For example, when numerous bids are received in a combinatorial auction, it is difficult to calculate an allocation of items to bidders wherein the seller retains some items (if appropriate) yet maximizes revenue for the seller.
Consequently, a large interest exists in solving the WDP and optimizing bid strategies in combinatorial auctions.